package fundamentals;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Stack;

/**
 * Dijkstra双栈算术表达式求值算法
 */
public class Evaluate {
    public static void main(String[] args) {
        //操作符栈
        Stack<String> ops = new Stack<>();
        //操作数栈
        Stack<Double> vals = new Stack<>();
        while (!StdIn.isEmpty()) {
            //读取字符，如果是操作符就压入ops
            String s = StdIn.readString();
            if ("(".equals(s)) ;
            else if ("+".equals(s)) ops.push(s);
            else if ("-".equals(s)) ops.push(s);
            else if ("*".equals(s)) ops.push(s);
            else if ("/".equals(s)) ops.push(s);
            else if ("sqrt".equals(s)) ops.push(s);
            else if (")".equals(s)) {
                //如果字符是），弹出运算符和操作数，并将运算结果压入栈
                String op = ops.pop();
                double v = vals.pop();
                if ("+".equals(op)) v = vals.pop() + v;
                else if ("+".equals(op)) v = vals.pop() + v;
                else if ("-".equals(op)) v = vals.pop() - v;
                else if ("*".equals(op)) v = vals.pop() * v;
                else if ("/".equals(op)) v = vals.pop() / v;
                else if ("sqrt".equals(op)) v = Math.sqrt(v);
                vals.push(v);
            }
            //将操作数压入vals
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}
